package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-12 14:14
 **/
public class LeetCode46 {
    //回溯
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        for (int i : nums) {
            list2.add(i);
        }
        backtrace(nums, list, list2, 0, n);
        return list;
    }

    void backtrace(int[] nums, List<List<Integer>> list, List<Integer> list2, int first, int n) {
        if (first == n) {
            list.add(new ArrayList(list2));
        }

        for (int i = first; i < n; ++i) {
            Collections.swap(list2, i, first);
            backtrace(nums, list, list2, first + 1, n);
            Collections.swap(list2, i, first);
        }
    }

    //排序+字典序+递归
    /*public List<List<Integer>> permute(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        int n = nums.length - 1;
        recur(nums, list, n);
        return list;
    }

    void recur(int[] nums, List<List<Integer>> list, int len) {
        //将初始值添加到数组中
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            temp.add(nums[i]);
        }

        list.add(temp);
        int index1 = len - 1;

        while (index1 >= 0 && nums[index1] >= nums[index1 + 1]) {
            --index1;
        }

        //是否存在更大的排列 true: 存在 false: 不存在
        boolean flag = index1 != -1;
        if (!flag) {
            return;
        }


        int index2 = len;
        while (index2 >= 0 && nums[index2] <= nums[index1]) {
            --index2;
        }
        swap(nums, index1, index2);
        reverse(nums, index1 + 1, len);
        recur(nums, list, len);
    }

    void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i, j);
            ++i;
            --j;
        }
    }

    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }*/

    public static void main(String[] args) {
        LeetCode46 code = new LeetCode46();
        System.out.println(code.permute(new int[]{1,2,3}));
    }

}
